package com.lee.common.util;

/**
 * “优先级队列”，《算法导论》6.5章节 原文摘要： A priority queue is a data structure for
 * maintaining a set S of elements, each with an associated value called a key.
 * A max-priority queue supports the following operations. • INSERT(S, x)
 * inserts the element x into the set S. This operation could be written as S←
 * S{x}. • MAXIMUM(S) returns the element of S with the largest key. •
 * EXTRACT-MAX(S) removes and returns the element of S with the largest key. •
 * INCREASE-KEY(S, x, k) increases the value of element x's key to the new value
 * k, which is assumed to be at least as large as x's current key value.
 * 堆的一种实际应用，可用于任务调度队列等。包含四个操作方法。 原文地址：
 * http://mushiqianmeng.blog.51cto.com/3970029/743611
 * 二叉堆
 * @author lihzh(苦逼coder)
 */
public class PriorityQueue {

	private final int DEFAULT_CAPACITY_VALUE = 16;
	// 初始化一个长度为16的队列（可作为构造参数)，此处选择16参考HashMap的初始化值
	private int capacity = DEFAULT_CAPACITY_VALUE;
	private int[] quene = new int[capacity];
	// 堆大小
	private int heapSize = 0;

	/**
	 * 返回当前最大值
	 * 
	 * @return
	 */
	public int maximum() {
		return quene[0];
	}

	/**
	 * 往优先级队列出，插入一个元素 利用INCREASE-Key方法，从堆的最后增加元素 伪代码： MAX-HEAP-INSERT(A, key) 1
	 * heap-size[A] ← heap-size[A] + 1 2 A[heap-size[A]] ← -∞ 3
	 * HEAP-INCREASE-KEY(A, heap-size[A], key) 时间复杂度：O(lg n)
	 * 
	 * @param value
	 *            待插入元素
	 */
	public void insert(int value) {
		// 注意堆容量和数组索引的错位 1
		quene[heapSize] = value;
		heapSize++;
		increaceKey(heapSize, value);
	}

	/**
	 * 增加给定索引位元素的值，并重新构成MaxHeap。 新值必须大于等于原有值 伪代码： HEAP-INCREASE-KEY(A, i, key) 1
	 * if key < A[i] 2 then error "new key is smaller than current key" 3 A[i] ←
	 * key 4 while i > 1 and A[PARENT(i)] < A[i] 5 do exchange A[i] ↔
	 * A[PARENT(i)] 6 i ← PARENT(i) 时间复杂度：O(lg n)
	 * 
	 * @param index
	 *            索引位
	 * @param newValue
	 *            新值
	 */
	public void increaceKey(int heapIndex, int newValue) {
		if (newValue < quene[heapIndex - 1]) {
			System.err.println("错误：新值小于原有值！");
			return;
		}
		quene[heapIndex - 1] = newValue;
		int parentIndex = heapIndex / 2;
		while (parentIndex > 0 && quene[parentIndex - 1] < newValue) {
			int temp = quene[parentIndex - 1];
			quene[parentIndex - 1] = newValue;
			quene[heapIndex - 1] = temp;
			heapIndex = parentIndex;
			parentIndex = parentIndex / 2;
		}
	}

	/**
	 * 返回堆顶元素（最大值），并且将堆顶元素移除 伪代码： HEAP-EXTRACT-MAX(A) 1 if heap-size[A] < 1 2
	 * then error "heap underflow" 3 max ← A[1] 4 A[1] ← A[heap-size[A]] 5
	 * heap-size[A] ← heap-size[A] - 1 6 MAX-HEAPIFY(A, 1) 7 return max
	 * 时间复杂度：O(lg n),
	 * 
	 * @return
	 */
	public int extractMax() {
		if (heapSize < 1) {
			System.err.println("堆中已经没有元素!");
			return -1;
		}
		int max = quene[0];
		quene[0] = quene[heapSize - 1];
		heapSize--;
		maxHeapify(quene, 1);
		return max;
	}

	/**
	 * 之前介绍的保持最大堆的算法
	 * 
	 * @param array
	 * @param index
	 */
	private void maxHeapify(int[] array, int index) {
		int l = index * 2;
		int r = l + 1;
		int largest;
		// 如果左叶子节点索引小于堆大小，比较当前值和左叶子节点的值，取值大的索引值
		if (l <= heapSize && array[l - 1] > array[index - 1]) {
			largest = l;
		} else {
			largest = index;
		}
		// 如果右叶子节点索引小于堆大小，比较右叶子节点和之前比较得出的较大值，取大的索引值
		if (r <= heapSize && array[r - 1] > array[largest - 1]) {
			largest = r;
		}
		// 交换位置，并继续递归调用该方法调整位置。
		if (largest != index) {
			int temp = array[index - 1];
			array[index - 1] = array[largest - 1];
			array[largest - 1] = temp;
			maxHeapify(array, largest);
		}
	}

	public static void main(String[] args) {
		PriorityQueue q = new PriorityQueue();
		q.insert(2);
		q.insert(6);
		q.insert(3);
		q.insert(8);
		q.insert(7);
		q.insert(9);
		q.insert(1);
		q.insert(10);
		q.insert(9);
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		q.insert(9);
		q.insert(1);
		q.insert(10);
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
		System.out.println(q.extractMax());
	}
}